/*
 *     Copyright (c) 2021. cc01cc. All rights reserved.
 *
 *     This file is part of this file.
 *
 *     This file is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Affero General Public License as published
 *     by the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     This file is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Affero General Public License for more details.
 *
 *     You should have received a copy of the GNU Affero General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <stdio.h>
#include <stdlib.h>

struct Triangle
{
     int row;
     int column;
     int value;
     int origin_value;
//         the index of child node.
     int i_path_from;
};
typedef struct Triangle Triangle;

void getData(Triangle *triangle, int n_line);
void findMax(Triangle *triangle, int n_line);
void printRoute(Triangle *triangle,int n_line);
int main()
{


//    the max of line is 20;
    const int max_line = 20;
    const int max_data = max_line*(max_line+1)/2;

//    the number of line.
    int n_line = 0;

    Triangle triangle[max_data];

    printf("please enter the number of line: ");
    scanf("%d", &n_line);
//    printf("n_line is %d\n", n_line);
    if(n_line > max_line || n_line == 0) return 0;

    getData(triangle, n_line);
    findMax(triangle, n_line);

    printf("The max value is %d.\n", triangle[0].value);

    printRoute(triangle, n_line);
}

/*
*   @function read and store data from the file "tower.txt".
*/
void getData(Triangle *triangle, int n_line)
{
    int i_triangle = 0;
    int i, j;
    freopen("tower.txt", "r", stdin);

    for(i = 0; i < n_line; i++)
    {
        for(j = 0; j < i + 1; j++)
        {
//            i_triangle = (i+1)(i+2)/2-1+j;
            triangle[i_triangle].row = i;
            triangle[i_triangle].column = j;
            scanf("%d", &triangle[i_triangle].origin_value);
            triangle[i_triangle].value = triangle[i_triangle].origin_value;
//            printf("the index, value is\t%d\t%d\n", i_triangle, triangle[i_triangle].value);
            i_triangle++;
        }
    }
}

void findMax(Triangle *triangle, int n_line)
{
    int i_triangle = 0;
    int i, j;
//    i_triangle--;
//    Index from the second to last line.
    i_triangle = n_line*(n_line-1)/2 - 1;
    for(i = n_line-1-1, j = 0; i >= 0; i--)
    {
        for(j = i; j >= 0; j--)
        {
//            printf("i_triangle, i, j is\t%d\t%d\t%d\n", i_triangle, i, j);
            if(triangle[i_triangle+i+2].value < triangle[i_triangle+i+1].value)
            {
                triangle[i_triangle].value=triangle[i_triangle].value+triangle[i_triangle+i+1].value;
                triangle[i_triangle].i_path_from = i_triangle+i+1;
//                printf("the index, value, i_path_from is\t%d\t%d\t%d\n", i_triangle, triangle[i_triangle].value, triangle[i_triangle].i_path_from);

            }else
            {
                triangle[i_triangle].value=triangle[i_triangle].value+triangle[i_triangle+i+2].value;
                triangle[i_triangle].i_path_from = i_triangle+i+2;
//                printf("the index, value, i_path_from is\t%d\t%d\t%d\n", i_triangle, triangle[i_triangle].value, triangle[i_triangle].i_path_from);
            }
//            printf("the index, value, i_path_from is\t%d\t%d\t%d\n", i_triangle, triangle[i_triangle].value, triangle[i_triangle].i_path_from);
            i_triangle--;
        }
    }
}

void printRoute(Triangle *triangle, int n_line)
{
    int i, j;
    int i_triangle = 0;
    printf("The route is %d", triangle[i_triangle].origin_value);
    for(i = 0; i < n_line - 1; i++)
    {
        i_triangle = triangle[i_triangle].i_path_from;
        printf("->%d", triangle[i_triangle].origin_value);
    }
    return 0;
}
